#include "binarytree.h"

#ifndef BINARYTREE_CPP
#define BINARYTREE_CPP

/* copy-constructor */
template< typename TKey, typename TData > 
BTree< TKey, TData >::BTree(const BTree< TKey, TData > &node) {
  mKey = node.key();
  mLeft = node.left();
  mRight = node.right();
  mParent = node.parent();
  mData = node.data();
}

template< typename TKey, typename TData > 
BTree< TKey, TData >::~BTree() {

  /* in case when non-root node is deleting */
  if (isParent()) {
    if (mParent->mLeft == this)
      mParent->mLeft = NULL;
    else if (mParent->mRight == this)
      mParent->mRight = NULL;
  }

  if ( isLeft() )
          delete mLeft;
  mLeft = NULL;

  if( isRight() ) 
          delete mRight;
  mRight = NULL;

};


template < typename TKey, typename TData >  
BTree < TKey, TData > &
BTree < TKey, TData > :: Min() const {
  BTree *cNode;
  cNode = this;
  while ( cNode->isLeft() )
          cNode = cNode->mLeft;
  return *cNode;
};

template < typename TKey, typename TData > 
BTree< TKey, TData > &
BTree < TKey, TData > :: Max() const {
	BTree *cNode;
	cNode = this;
	while ( cNode->right() )
		cNode = cNode->right();
	return *cNode;
};

/*
template < typename TKey, typename TData > 
void
BTree < TKey, TData > :: unlink() {
	
	BTree *min;
	
	if ( !this->right() ) 
		min = this->parent();
	else
		min = this->right()->Min();
	
		min = this->right()->Min();

};
*/
/*
* return values:
* BTree pointer to new entry
*/

template < typename TKey, typename TData >
BTree< TKey, TData > & 
BTree < TKey, TData >::insert( TKey aKey, TData aData ) {
	BTree *cNode, *pNode;

        /* add entry to the subtree with current root-node */
	cNode = this;
	pNode = NULL;

	while ( cNode ) {
		pNode = cNode;
		if ( aKey < cNode->mKey )
			cNode = cNode->mLeft;
		else
			cNode = cNode->mRight;
	}

	cNode = new BTree( aKey, aData, pNode );

	if ( aKey < pNode->mKey )
		pNode->setLeft( cNode );
	else
		pNode->setRight( cNode );

	return cNode;

}

template < typename TKey, typename TData >
void
BTree < TKey, TData >::add( TKey aKey, TData aData ) {
  insert(aKey, aData);
};

template < typename TKey, typename TData >
void
BTree < TKey, TData >::treatmentTree( BTree < TKey, TData> *subTree, void eval( TData *aData ) ) {
  if ( subTree == NULL )
    return;
  /* recursive algorithm is realised */
  if ( subTree->isLeft() )
    treetmentTree( subTree->left(), eval );

  eval( subTree->pData() );

  if ( subTree->isRight() )
    treetmentTree( subTree->right(), eval );
  
};
/*
 * return values:
 * NULL - entry not found
 */
template < typename TKey, typename TData > 
BTree< TKey, TData > * 
BTree < TKey, TData >::search( const TKey aKey ) const {

	BTree *cNode = this;

	while ( cNode ) {
		if ( aKey < cNode->key() )
			cNode = cNode->left();
		else if ( aKey == cNode->key() )
			return cNode;
		else
			cNode = cNode->right();

	}

	return NULL;
};

template < typename TKey, typename TData > 
bool
BTree < TKey, TData >::find( TKey aKey ) const {
  if (search(aKey))
    return true;
  return false;
};

/* 
 * return values:
 * true - ok
 * false - key hasn't found
 * */
template < typename TKey, typename TData > 
bool 
BTree < TKey, TData >::rm( TKey aKey ) {
  BTree *cNode = NULL, *minNode = NULL, *cParent = NULL;
  bool result = true;

/*
 * if val is not one while-loop needs to add
 */

  if ( (cNode = search( aKey )) == NULL ) {
    result = false;
    return result;
  }
  
  cParent = cNode->mParent;

  if ( cNode->mRight ) {
    cParent->setLeft( cNode->mRight );
    if ( cNode->mLeft ) {
      while ( minNode->mLeft )
              minNode = minNode->mLeft;
      minNode->setLeft( cNode->mLeft );
    }
  } else if ( cNode->mLeft ) {
    cParent->setLeft( cNode->mLeft );
  }

  delete cNode;

  return result;
};

/*
 * true - ok, key has been changed
 * false - key nasn't been found or something else
 */
template < typename TKey, typename TData > 
bool 
BTree < TKey, TData >::replace( const TKey oldKey, const TKey newKey ) {
  BTree *replaceNode = NULL;
  TData cData;
  BTree * cParent, cNode;
  bool tagLeft = true;
  bool result = true;

  /* what if oldKey doesn't exist? */
  /*
  if ( oldKey == newKey )
          return true; */ /* return ok */

  /* Unlink node */
  if ( (replaceNode = search( oldKey )) == NULL ) {
    /* result is used only for debug purpose  */
    result = false;
    return result; /* old key nas not found */
  } 

  /* oldKey exists */
  if ( oldKey == newKey )
          return result; /* return ok */

  cParent = replaceNode->mParent;
  cNode = cParent;
  /* we should to take a lager node and put it to parent node */
  /* is replaceable node left child? */
  if ( cParent->mLeft != replaceNode )
    tagLeft = false;
  /* if right child exists it should to replace this node */
  if ( replaceNode->mRight ) {
    if ( tagLeft )
      cNode->setLeft( replaceNode->mRight );
    else {
      cNode->setRight( replaceNode->mRight);
      cNode = cNode->mRight;
    }
  }

  /* add to the left smaller node */
  cNode->Min().setLeft( replaceNode->left() ? replaceNode->left() : NULL );

  /* Link node */
  cNode = this;
  cParent = NULL;
  replaceNode->mKey = newKey;

  while ( cNode ) {
    /* go to the next node */
    cParent = cNode;
    if ( newKey < cNode->mKey )
      cNode = cNode->mLeft;
    else
      cNode = cNode->mRight;
  }

  /* to link! */
  if ( newKey < mParent->mKey )
    cParent->mLeft = replaceNode;
  else
    cParent->mRight = replaceNode;

  return result;
};

#endif 
